/*
 * Click nbfs://nbhost/SystemFileSystem/Templates/Licenses/license-default.txt to change this license
 * Click nbfs://nbhost/SystemFileSystem/Templates/Classes/Class.java to edit this template
 */
package com.sx.sx1.lintcode.day717;

import java.util.*;

/**
 *
 * @author Administrator
 */
public class LC911 {

    static class Solution {

        /**
         * @param nums: an array
         * @param k: a target value
         * @return: the maximum length of a subarray that sums to k
         */
        public int maxSubArrayLen(int[] nums, int k) {
            /*
            这题要和leetCode209.长度最小的子数组滑动窗口玩法分开
            难点，在于理解（前缀和-目标值）这其实就可以理解
            求数组其中一段是不是等于目标值（其实就是某一段前缀和-这一段前缀和之前的的前缀和=目标值）
            其实就是判断（减法中减数是不是在其中）
             */

            int n = nums.length;
            if (n == 1 && nums[0] == k) {
                return 1;
            }
            int ans = Integer.MIN_VALUE;

            //k: 前缀和  v: 下标
            Map<Integer, Integer> pmap = new HashMap<>();
            pmap.put(0, -1); //因为我们要比较最前面的一段，所以要将-1的位置赋值为0
            int sum = 0;
            for (int i = 0; i < n; i++) {
                sum += nums[i];
                // 放到map中(因为我们的题意是求最长的，所以记录第一次就行了，后面再有一样得前缀和，其实对我们得结果没有影响)
                if (!pmap.containsKey(sum)) {
                    pmap.put(sum, i);
                }

                //判断长度
                if (pmap.containsKey(sum - k)) {

                    int idx = pmap.get(sum - k);

                    if (ans < i - idx) {

                        ans = i - idx;
                    }
                }
            }
            return ans == Integer.MIN_VALUE ? 0 : ans;
        }
    }

    public static void main(String[] args) {
        Solution obj = new Solution();
        int[] nums = {1, -1, 5, -2, 3};
        int k = 3;
        System.out.println(obj.maxSubArrayLen(nums, k));
        int[] nums1 = {-2, -1, 2, 1};
        int k1 = 1;
        System.out.println(obj.maxSubArrayLen(nums1, k1));

        System.out.println(obj.maxSubArrayLen(new int[]{1, 0, -1}, 0));
    }
}


/*
[1,0,-1]
0
输出数据
0
期望答案
3


911 · 最大子数组之和为k
算法
中等
通过率
52%
题目
题解26
笔记77
讨论2
排名
记录
描述
给一个数组nums和目标值k，找到数组中最长的子数组，使其中的元素和为k。如果没有，则返回0。

北美在招WLB&高薪厂面经曝光

微信加sunny【jiuzhang1104】备注【在招】即可领取


数组之和保证在32位有符号整型数的范围内
数组范围：
0
≤
len
(
nums
)
≤
15000
0≤len(nums)≤15000
数组元素范围：
−
3000
≤
nums
[
�
]
≤
3000
−3000≤nums[i]≤3000

样例
样例1

输入: nums = [1, -1, 5, -2, 3], k = 3
输出: 4
解释:
子数组[1, -1, 5, -2]的和为3，且长度最大
样例2

输入: nums = [-2, -1, 2, 1], k = 1
输出: 2
解释:
子数组[-1, 2]的和为1，且长度最大
挑战
能否用O(n)的时间复杂度完成？
 */
